package com.explorati.binarysearch;

import java.time.Instant;

public class BinarySearch {
	public static int binarySearch(Comparable[] arr, Integer target) {
		int n = arr.length - 1;
		// 在[l...r]的范围内寻找target
		int l = 0, r = n;
		// 当l = r时，区间[l...r]依然是有效的
		while (l <= r) {
			int mid = l + (r - l) / 2;
			if (target.compareTo(mid) > 0) {
				// target在[mid + 1...r]中
				l = mid + 1;
			} else if (target.compareTo(mid) < 0) {
				// target在[l...mid - 1]中
				r = mid - 1;
			} else {
				return mid;
			}
		}
		return -1;
	}

	public static void main(String[] args) {
		int n = (int) Math.pow(10, 7);
		Integer[] data = Util.generateOrderArray(n);

		// long startTime = Instant.now().toEpochMilli();
		// long startTime = System.currentTimeMillis();
		long startTime = System.nanoTime();
		int index = binarySearch(data, (int) Math.random() * n);
		if (index < 0) {
			throw new IllegalStateException("find i failed!");
		}
		long endTime = System.nanoTime();
		// long endTime = System.currentTimeMillis();
		// long endTime = Instant.now().getNano();
		// long endTime = Instant.now().toEpochMilli();
		System.out.println("Binary Search test complete!");
		System.out.println("Time cost：" + (endTime - startTime) + " ns");

	}
}
